删除边不好做,考虑将操作离线倒着加边。
考虑连边时维护割边。
-
不联通,直接连上即可,可以看出,这条边是割边。
-
已经联通,说明构成一个环,原来在 路径上的边都不再是割边。
如果把割边的值设为 ,非割边的值设为 ,那么只需要修改和维护链的和即可。
因为根会变,所以边的信息需要新建点来存储。
#include <map>
#include <cstdio>
#include <iostream>
using namespace std;
const int MAXN = 2e5;
struct node {
int ch[ 2 ] , fa;
int val , Sum;
bool rev , cov;
};
struct LinkCutTree {
node Tree[ MAXN + 5 ];
#define ls( x ) Tree[ x ].ch[ 0 ]
#define rs( x ) Tree[ x ].ch[ 1 ]
void Pushup( int x ) {
Tree[ x ].Sum = Tree[ ls( x ) ].Sum + Tree[ x ].val + Tree[ rs( x ) ].Sum;
}
void Reverse( int x ) { swap( ls( x ) , rs( x ) ); Tree[ x ].rev ^= 1; }
void Cov( int x ) { Tree[ x ].Sum = Tree[ x ].val = 0; Tree[ x ].cov = 1; }
void Pushdown( int x ) {
if( Tree[ x ].rev ) {
if( ls( x ) ) Reverse( ls( x ) );
if( rs( x ) ) Reverse( rs( x ) );
Tree[ x ].rev = 0;
}
if( Tree[ x ].cov ) {
if( ls( x ) ) Cov( ls( x ) );
if( rs( x ) ) Cov( rs( x ) );
Tree[ x ].cov = 0;
}
}
bool isrt( int x ) { //是否为 splay 的 rt
return ls( Tree[ x ].fa ) != x && rs( Tree[ x ].fa ) != x;
}
bool chk( int x ) { return rs( Tree[ x ].fa ) == x; }
void Rotate( int x ) {
int y = Tree[ x ].fa , z = Tree[ y ].fa , p = chk( x ) , a = Tree[ x ].ch[ !p ];
if( !isrt( y ) ) Tree[ z ].ch[ chk( y ) ] = x; Tree[ x ].fa = z;
Tree[ x ].ch[ !p ] = y; Tree[ y ].fa = x;
Tree[ y ].ch[ p ] = a; if( a ) Tree[ a ].fa = y;
Pushup( y );
}
void Pushcn( int x ) { //pushdown 根到x
if( !isrt( x ) ) Pushcn( Tree[ x ].fa );
Pushdown( x );
}
void Splay( int x ) {
Pushcn( x );
while( !isrt( x ) ) {
int y = Tree[ x ].fa , z = Tree[ y ].fa;
if( !isrt( y ) ) Rotate( chk( x ) == chk( y ) ? y : x );
Rotate( x );
}
Pushup( x );
}
void Access( int x ) {
for( int y = 0 ; x ; y = x , x = Tree[ x ].fa )
Splay( x ) , rs( x ) = y , Pushup( x );
}
void Makeroot( int x ) {
Access( x ); Splay( x );
Reverse( x );
}
int Findroot( int x ) {
Access( x ); Splay( x );
for( ; ls( x ) ; x = ls( x ) ) Pushdown( x );
Splay( x ); return x;
}
bool Connected( int u , int v ) {
Makeroot( u ); return Findroot( v ) == u;
}
bool Link( int u , int v ) {
if( Connected( u , v ) ) {
Split( u , v ); Cov( v );
return 0;
}
Tree[ u ].fa = v; return 1;
}
bool Cut( int u , int v ) {
if( !Connected( u , v ) ) return 0;
if( ls( v ) || Tree[ v ].fa != u ) return 0;
Tree[ v ].fa = 0; rs( u ) = 0;
return 1;
}
void Split( int u , int v ) {
Makeroot( u ); Access( v ); Splay( v );
}
}LCT;
struct Query {
int op , u , v , Ans;
}Qry[ MAXN + 5 ];
map< int , bool > Graph[ MAXN + 5 ];
int n , m , q , cnt;
int main( ) {
scanf("%d %d",&n,&m);
for( int i = 1 , u , v ; i <= m ; i ++ ) {
scanf("%d %d",&u,&v);
Graph[ u ][ v ] = Graph[ v ][ u ] = 1;
LCT.Tree[ n + i ].val = 1;
}
for( ; scanf("%d",&Qry[ ++ q ].op) && Qry[ q ].op != -1 ; ) {
scanf("%d %d",&Qry[ q ].u,&Qry[ q ].v);
if( Qry[ q ].op == 0 ) Graph[ Qry[ q ].u ][ Qry[ q ].v ] = Graph[ Qry[ q ].v ][ Qry[ q ].u ] = 0;
} q --;
for( int i = 1 ; i <= n ; i ++ )
for( auto v : Graph[ i ] )
if( v.second != 0 && v.first > i ) {
cnt ++;
LCT.Link( i , n + cnt );
LCT.Link( n + cnt , v.first );
//printf("%d %d\n", i , v.first );
}
for( int i = q ; i >= 1 ; i -- ) {
if( Qry[ i ].op == 0 ) {
cnt ++;
LCT.Link( Qry[ i ].u , n + cnt );
LCT.Link( n + cnt , Qry[ i ].v );
}
if( Qry[ i ].op == 1 ) {
LCT.Split( Qry[ i ].u , Qry[ i ].v );
Qry[ i ].Ans = LCT.Tree[ Qry[ i ].v ].Sum;
}
}
for( int i = 1 ; i <= q ; i ++ )
if( Qry[ i ].op == 1 ) printf("%d\n", Qry[ i ].Ans );
return 0;
}